Computer systems transfer and store data in many different formats on many different types of media. For example, busses and networks are used for high speed transfer of data streams, while disk and tape drives are used for sequential storage of large blocks of data segments. Regardless of the type of storage medium or the transfer means used, each data segment transferred and stored must be uniquely identifiable in order to distinguish it from other data segments.
Data segments such as data blocks on magnetic and optical disks, data blocks on tape, packets transferred over a network, or data messages on message based busses typically have associated with them a field for unique identification. Such data segments may also have other types of unique identification fields associated with them; for instance, password fields, record numbers, time stamps, node IDs, or the like. Reliable means for storing and retrieving these unique identification fields is required in order to prevent errors and data corruption that can occur when a unique identification field is improperly retrieved or corrupted.
On magnetic disks, for example, data is stored in circular tracks. Each track is divided into a number of data blocks usually consisting of a fixed number of bytes. Each data block usually consists of two sections, a header section and a data section. The data blocks on the disk are uniquely identified by physical address identification fields recorded in the header sections of the data blocks. The physical address field is a three dimensional field indicating sector, disk surface, and track number.
A disk drive has one or more read/write heads which must be positioned over data blocks to perform read or write operations on those blocks. Each head is associated with one disk surface. The radial positioning of the heads is typically controlled by a single head positioner. Thus when a read or write operation is to be performed to a particular data block, the head positioner moves the heads radially to the position of the track containing the block. Disk rotation then moves the successive blocks in the selected track under the head.
The selected head must read each data block header as it moves by and determine whether or not the data block is the requested block. This determination must be made by the time the end of the physical address identification field associated with the data block has reached the read/write head. That is, if the drive is to perform a read or write operation to a data block, it must be ready to do so when the data portion of the data block, which closely follows the header portion, rotates under the head.
In order to determine if a data block is the requested data block, the drive reads the physical address identification field from the disk and then compares it with the specified address of the data block in which data is to be read or written. If the addresses match, the data will be read from or written to the sector.
If an address identification field as read from a data block contains any errors, the data block may be mistakenly identified as another data block. Thus when the head is actually located over data block 100, the address may, for example, be identified as data block 101 because of a bit error, and the read or write operation that is to occur at data block 101 will be performed in the wrong location.
In the past, one or a combination of various methods have been used to protect the header fields of data blocks on disks or blocks on tapes, such as cyclic redundancy code (CRC), redundant copies of fields, and error correction codes (ECC).
According to the redundant copies of fields method, the physical address identification field is recorded several times in succession. The specified address is compared with each copy of the address identification fields stored in the data block header, and if some minimum number of retrieved address identification fields match the specified address the data block is determined to be the requested data block. Thus, if one of the copies of the address identification field contains an error, the data block will still be identifiable. This method, however, increases the data surface area required for the storage of the header field, thus reducing the data capacity of the disk. The surface area required for storage of the address identification fields increases, no less, as the error rate increases, since more copies of the address identification fields must be stored to satisfy required reliability specifications.
The more efficient CRC and ECC methods add redundancy bits to the physical address identification field in the header in such a way that errors can be detected. ECC utilizes further processing of the encoded address field to allow for correction of limited numbers of bit errors. ECC, however, requires time consuming calculations for corrections, and therefore requires a gap on the disk between the header and data fields, increasing the effective area used by the header information. Also, though both methods supply some fault tolerance and require less storage space than the address redundancy method, each still increases the data storage area required for the storage of the header field due to the extra bits required.
There is a longstanding need for a method of storing and locating unique identification fields associated with data segments such that the utilization of medium area for header information is minimized while the necessary fault tolerance, simplicity, speed, uniqueness, and robust detection are provided.